package com.sourcetrip.raw.adt;

import com.sourcetrip.raw.adt.abs.MyAbstractBinarySearchTree;
import com.sourcetrip.raw.model.MyBinaryNode;

import java.util.Stack;

/**
 * @author: ZhouBert
 * @date: 2020/11/24
 * @description: 我的二叉搜索树
 * 其中的元素必须得具有可比较性，那么 null 就不能作为其中的元素！
 */
public class MyBinarySearchTree<E extends Comparable> extends MyAbstractBinarySearchTree<E> {

	/**
	 * 指向根节点
	 */
	//private MyBinaryNode<E> root;
	@Override
	public void clear() {

	}

	/**
	 * 添加元素（假设树中没有值相等的元素）
	 * 1.根节点的处理；
	 * 2.非根节点：二叉查找；（但是根节点是不动的，所以这种结构是可能会退化为链表的）
	 * -1-找到 父节点；
	 * -2-创建 新节点，parent.left=node or parent.right=node
	 *
	 * @param element
	 */
	@Override
	public void add(E element) {
		//根节点：root 指向新的节点
		if (size == 0) {
			root = new MyBinaryNode<>(element, null);
			//默认将 guard 的 left 指向 root
//			guard.setLeft(root);
			size++;
			return;
		}
		//非根节点
		//1.拿到 目标节点的父节点
		MyBinaryNode<E> pNode = getParentNode(element, root);
		//element 小于父节点 -> 挂在左边
		if (pNode.getElement().compareTo(element) > 0) {
			pNode.setLeft(new MyBinaryNode<>(element, pNode));
		} else {
			pNode.setRight(new MyBinaryNode<>(element, pNode));
		}
		size++;
	}

	/**
	 * 通过二分查找找到父节点(node 节点下)
	 * （假设树中没有值相等的元素）
	 *
	 * @param element
	 * @param node    节点
	 * @return
	 */
	private MyBinaryNode<E> getParentNode(E element, MyBinaryNode<E> node) {
		//如果既要挂在 node 下面，同时又是一个叶子节点，就直接返回
		if (node.getRight() == null && node.getLeft() == null) {
			//直接返回该作为父节点
			return node;
		}
		//greater than element-> left
		if (node.getElement().compareTo(element) > 0) {
			if (node.getLeft() == null) {
				return node;
			}
			return getParentNode(element, node.getLeft());
		} else {
			if (node.getRight() == null) {
				return node;
			}
			return getParentNode(element, node.getRight());
		}
	}

	/**
	 * 通过二分查找找到相同的节点(node 节点下)
	 *
	 * @param element
	 * @param node
	 * @return
	 */
	private MyBinaryNode<E> getTheNode(E element, MyBinaryNode<E> node) {
		if (node == null) {
			return null;
		}
		//返回相同
		if (node.getElement().compareTo(element) == 0) {
			return node;
		}
		//当 node 没有对应的 度时进行返回
		if (node.getElement().compareTo(element) > 0) {
			if (node.getLeft() == null) {
				return null;
			}
			return getTheNode(element, node.getLeft());
		} else {
			if (node.getRight() == null) {
				return null;
			}
			return getTheNode(element, node.getRight());
		}
	}

	/**
	 * 移除
	 * （此时要找到树中存在值相等的元素，那么方法就跟 getParentNode 不一样）
	 * 1.找到相等的节点
	 * 2.通过 Parent Node 进行移除
	 *
	 * @param element
	 */
	@Override
	public void remove(E element) {
		if (size == 0) {
			throw new RuntimeException("没有元素可以用于删除！");
		}
		MyBinaryNode<E> cur = this.root;
		MyBinaryNode<E> prev = null;
		while (cur != null) {
			if (cur.getElement().compareTo(element) == 0) {
				break;
			}
			prev = cur;
			if (cur.getElement().compareTo(element) > 0) {
				cur = cur.getLeft();
			} else {
				cur = cur.getRight();
			}
		}

		if (cur == null) {
			//没有找到元素--> 直接返回
			return;
		}
		//找到元素--> 进行删除
		//1.如果找到的是头节点，先统一处理，避免代码太突兀了！
		//region	没有利用 guard 的版本
		if (prev == null && !(cur.getLeft() != null && cur.getRight() != null)) {
			if (cur.getLeft() == null && cur.getRight() == null) {
				root = null;
			} else if (cur.getLeft() != null) {
				root = cur.getLeft();
				root.setParent(null);
			} else if (cur.getRight() != null) {
				root = cur.getRight();
				root.setParent(null);
			}
			return ;
		}
		//endregion

		//2.接下来就可以不用考虑头节点了
		//但是使用了 哨兵节点，考虑一下写法
		//哨兵节点有冲突，而且其实指向不明确，暂时不用哨兵了
		if (cur.getLeft() == null && cur.getRight() == null) {
			if (prev.getLeft() == cur) {
				prev.setLeft(null);
			} else {
				prev.setRight(null);
			}
			size--;
			afterRemove(cur);
		} else if (cur.getLeft() != null && cur.getRight() == null) {
			if (prev.getLeft() == cur) {
				prev.setLeft(cur.getLeft());
			} else {
				prev.setRight(cur.getLeft());
			}
			//修复子的 parent
			cur.getLeft().setParent(prev);
			size--;
			afterRemove(cur);
		} else if (cur.getRight() != null && cur.getLeft() == null) {
			if (prev.getLeft() == cur) {
				prev.setLeft(cur.getRight());
			} else {
				prev.setRight(cur.getRight());
			}
			cur.getRight().setParent(prev);
			size--;
			afterRemove(cur);
		} else {
			//两个节点都有
			MyBinaryNode<E> predecessor = cur.getLeft();
			while (predecessor.getRight() != null) {
				predecessor = predecessor.getRight();
			}
			//此时找到了 前驱节点
			//先删除 前驱节点
			remove(predecessor.getElement());
			cur.setElement(predecessor.getElement());
		}

	}


	/**
	 * 删除的节点
	 * @param deletedNode
	 */
	protected void afterRemove(MyBinaryNode<E> deletedNode) {

	}

	/**
	 * 查询对应的元素，如果为 null -> false
	 *
	 * @param element
	 * @return
	 */
	@Override
	public boolean contains(E element) {
		MyBinaryNode<E> theNode = getTheNode(element, root);
		return theNode != null;
	}

	public static void inorderPrintTree(MyBinarySearchTree tree) {
		inorderPrintNode(tree.root);
	}

	static void inorderPrintNode(MyBinaryNode node) {
		if (node == null) {
			return;
		}

		inorderPrintNode(node.getLeft());
		System.out.print(node + " ");
		inorderPrintNode(node.getRight());
	}

	/**
	 * 先序遍历的循环写法
	 * 不对，想的不完整，得重新想一下！
	 *
	 * @return
	 */
	@Override
	public String toString() {
		//暂时做一个先序遍历吧//先序遍历的循环写法是有点难写
		// 但是如果图画起来的话，可以发现，是通过一个栈进行辅助实现的！
		// 栈里面需要存的就是每一个根节点
		StringBuilder sb = new StringBuilder();
		sb.append("[");
		//region	old version is wrong
//		if (root != null) {
//			//辅助栈，协助完成树的先序遍历
//			Stack<MyBinaryNode<E>> rootStack = new Stack<>();
//			//根 左 右
//			MyBinaryNode<E> tempLeft = root.getLeft();
//			sb.append(root.getElement().toString());
//			rootStack.push(root);
//			while (tempLeft != null) {
//				sb.append(", ").append(tempLeft.getElement().toString());
//				//存放下一个子树的根节点
//				rootStack.push(tempLeft);
//				tempLeft = tempLeft.getLeft();
//			}
//			//此时已经执行完所有的左节点，即完成了 根-左 的打印，只需要完成 右 的打印即可！
//			//-> 逐个弹出栈里的根元素，对其右节点进行打印即可//不对，这里还需要去找左节点！这就麻烦了！
//			while (!rootStack.isEmpty()) {
//				MyBinaryNode<E> tempRoot = rootStack.pop();
//				//处理左节点
//				tempLeft = tempRoot.getLeft();
//				while (tempLeft != null) {
//					sb.append(", ").append(tempLeft.getElement().toString());
//					rootStack.push(tempLeft);
//					tempLeft = tempLeft.getLeft();
//				}
//				//对右节点不为空时，进行处理即可！
//				if (tempRoot.getRight() != null) {
//					sb.append(", ").append(tempRoot.getRight().getElement().toString());
//				}
//			}
//		}
		//endregion

		if (size == 0) {
			//直接返回
			return sb.append("]").toString();
		}

		//region	写算法必须得将整个流程都捋顺！再去写！
		//首先一个指针是很有必要的！//感觉最重要的是，完整地把握好流程，然后写好伪代码！
		//1.建立一个栈用于存放右子树还没处理的节点
		//里面的节点都是已经打印过了的
		Stack<MyBinaryNode<E>> waitRightDealingStack = new Stack<>();
		MyBinaryNode<E> cur = root;
		//因为这三个因素，都会是 cur 的下一个指向！
		//(既然这里不为null ,那么我就必须要在迭代中保证 cur 不会指向一个空指针！)
		while (cur.getLeft() != null || cur.getRight() != null || !waitRightDealingStack.isEmpty()) {
			sb.append(cur.getElement().toString()).append(", ");
			//根据 根-左-右 的规则，让 cur 指向下一个
			if (cur.getLeft() != null && cur.getRight() != null) {
				//让该节点入栈
				waitRightDealingStack.push(cur);
				//指向下一个
				cur = cur.getLeft();
			} else if (cur.getLeft() != null) {
				cur = cur.getLeft();
			} else if (cur.getRight() != null) {
				cur = cur.getRight();
			} else {
				//既然已经到这里，说明 cur.getLeft == null && cur.getRight==null && stack is not Empty
				//此时弹出栈顶元素，作为指向的下一个元素
				//跟上面区别的是：弹出的不需要另外打印！
				cur = waitRightDealingStack.pop().getRight();
			}
		}
		//此时 cur 指向最后一个节点
		sb.append(cur.getElement().toString());

		//endregion


		sb.append("]");
		return sb.toString();
	}
}
